// https://leetcode-cn.com/problems/binary-tree-paths/
/*
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
*/
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {};

};

class Solution {
public:
    vector <string> res = {};
    string s = ""; // 回溯写法

    vector <string> binaryTreePaths(TreeNode *root) {
//        back(root);
        string s1 = "";
        dfs(root, s1);
        return res;
    }

    // 这种方式速度和内存更好一点点
    void dfs(TreeNode *node, string s) {
        if (node) {
            s = s + "->" + to_string(node->val);
            if (node->left == nullptr && node->right == nullptr) {
                s = s.substr(2, s.size() - 2);
                res.push_back(s);
                return;
            }
            dfs(node->left);
            dfs(node->right);
        }
    }

    void back(TreeNode *node) {
        if (node) {
            if (node->left == nullptr && node->right == nullptr) {
                string tmpS = s + "->" + to_string(node->val);
                tmpS = tmpS.substr(2, tmpS.size() - 2);
                res.push_back(tmpS);
                return;
            }
            string beforeS = s;
            string tmp = "->" + to_string(node->val);
            s = s + tmp;
            back(node->left);
            back(node->right);
            s = beforeS;
        }
    }

    TreeNode *init2() {
        TreeNode *n1 = new TreeNode(1);
        TreeNode *n2 = new TreeNode(2);
        TreeNode *n3 = new TreeNode(3);
        TreeNode *n4 = new TreeNode(5);
        n1->left = n2;
        n1->right = n3;
        n3->right = n4;

        return n1;
    }
};

int main() {
    Solution so;
    TreeNode *head = so.init2();
    auto res = so.binaryTreePaths(head);
    for (auto i : res) {
        cout << i << endl;
    }
    return 0;
}